package cn.edu.xjtu.work.removeStrDuplicates;

import java.util.Stack;

/**
 * 1047. 删除字符串中的所有相邻重复项
 * 
 * 给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。
 * 
 * 在 S 上反复执行重复项删除操作，直到无法继续删除。
 * 
 * 在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。
 * 
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/remove-all-adjacent-duplicates-in-string
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Solution {
    public static void main(String[] args) {
        Solution solu = new Solution();
        System.out.println(solu.removeDuplicates("abbaca"));
    }

    /**
     * 用栈处理,类似括号匹配
     * 
     * @param s
     * @return
     */
    public String removeDuplicates(String s) {
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            if (!stack.isEmpty() && s.charAt(i) == stack.peek()) {
                stack.pop();
                continue;
            }
            stack.push(s.charAt(i));
        }
        StringBuilder sb = new StringBuilder();

        while (!stack.isEmpty()) {
            sb.append(stack.pop());
        }
        return sb.reverse().toString();
    }

    /**
     * 超时,104/106
     * 
     * @param s
     * @return
     */
    public String removeDuplicates1(String s) {
        StringBuilder sb = new StringBuilder();
        boolean flag = true;

        while (flag) {
            flag = false;
            sb = new StringBuilder();

            int i;
            for (i = 0; i < s.length() - 1; i++) {
                if (s.charAt(i) != s.charAt(i + 1)) {
                    sb.append(s.charAt(i));
                } else {
                    flag = true;
                    i++;
                }
            }
            if (i == s.length() - 1) {
                sb.append(s.charAt(i));
            }
            s = sb.toString();
        }

        return sb.toString();
    }
}
